package myTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class MyBTree {
    BTNode<Character> b;        //根结点
    String bstr;            //二叉树的括号表示串

    public MyBTree()        //构造方法
    {
        b = null;
    }

    //二叉树基本运算算法
    public void createBTree(String str) {
        Stack<BTNode> st = new Stack<BTNode>();     //建立一个栈st
        BTNode<Character> p = null;
        boolean flag = true;
        char ch;
        int i = 0;
        while (i < str.length())    //循环扫描str中每个字符
        {
            ch = str.charAt(i);
            switch (ch) {
                case '(':
                    st.push(p);        //刚刚新建的结点有孩子,将其进栈
                    flag = true;
                    break;
                case ')':
                    st.pop();        //栈顶结点的子树处理完，出栈
                    break;
                case ',':
                    flag = false;    //开始处理栈顶结点的右孩子
                    break;
                default:
                    p = new BTNode<Character>(ch);    //用ch值新建一个结点
                    if (b == null) b = p;        //若尚未建立根结点,p作为根结点
                    else            //已建立二叉树根结点
                    {
                        if (flag)        //新结点p作为栈顶结点的左孩子
                        {
                            if (!st.empty()) st.peek().lchild = p;
                        } else            //新结点p作为栈顶结点的右孩子
                        {
                            if (!st.empty()) st.peek().rchild = p;
                        }
                    }
                    break;
            }
            i++;                //继续遍历
        }
    }

    public String toString()            //返回二叉链的括号表示串
    {
        bstr = "";
        toString1(b);
        return bstr;
    }

    private void toString1(BTNode<Character> t) //被toString方法调用
    {
        if (t != null) {
            bstr += t.data;                //输出根结点值
            if (t.lchild != null || t.rchild != null) {
                bstr += "(";                //有孩子结点时输出"("
                toString1(t.lchild);            //递归输出左子树
                if (t.rchild != null) bstr += ",";            //有右孩子结点时输出","
                toString1(t.rchild);            //递归输出右子树
                bstr += ")";                //输出")"
            }
        }
    }

    public BTNode<Character> findNode(char x)    //查找值为x的结点算法
    {
        return findNode1(b, x);
    }

    private BTNode<Character> findNode1(BTNode<Character> t, char x)//被FindNode方法调用
    {
        BTNode<Character> p;
        if (t == null) return null;        //t为空时返回null
        else if (t.data == x) return t;                //t所指结点值为x时返回t
        else {
            p = findNode1(t.lchild, x);        //在左子树中查找
            if (p != null) return p;                //在左子树中找到p结点
            else return findNode1(t.rchild, x);    //返回在右子树中查找结果
        }
    }

    public int height()                //求二叉树高度的算法
    {
        return height1(b);
    }

    private int height1(BTNode<Character> t)    //被Height方法调用
    {
        int lchildh, rchildh;
        if (t == null) return 0;            //空树的高度为0
        else {
            lchildh = height1(t.lchild);        //求左子树高度lchildh
            rchildh = height1(t.rchild);        //求右子树高度rchildh
            return Math.max(lchildh, rchildh) + 1;
        }
    }

    public void preOrder1(MyBTree bt)        //先序遍历的递归算法
    {
        preOrder11(bt.b);
    }

    private void preOrder11(BTNode<Character> t) //被PreOrder1方法调用
    {
        if (t != null) {
            System.out.print(t.data + " ");        //访问根结点
            preOrder11(t.lchild);            //先序遍历左子树
            preOrder11(t.rchild);            //先序遍历右子树
        }
    }

    public void inOrder1(MyBTree bt)        //中序遍历的递归算法
    {
        inOrder11(bt.b);
    }

    private void inOrder11(BTNode<Character> t) //被InOrder1方法调用
    {
        if (t != null) {
            inOrder11(t.lchild);            //中序遍历左子树
            System.out.print(t.data + " ");        //访问根结点
            inOrder11(t.rchild);            //中序遍历右子树
        }
    }

    public void postOrder1(MyBTree bt)    //后序遍历的递归算法
    {
        postOrder11(bt.b);
    }

    private void postOrder11(BTNode<Character> t) //被PostOrder1方法调用
    {
        if (t != null) {
            postOrder11(t.lchild);            //后序遍历左子树
            postOrder11(t.rchild);            //后序遍历右子树
            System.out.print(t.data + " ");        //访问根结点
        }
    }

    public static int nodeCountPre(MyBTree bt) //基于先序遍历求结点个数
    {
        return nodeCountPre1(bt.b);
    }

    private static int nodeCountPre1(BTNode<Character> t) {
        int m, n, k;
        if (t == null)            //空树结点个数为0
            return 0;
        k = 1;                    //根结点计数1，相当于访问根结点
        m = nodeCountPre1(t.lchild);        //遍历求左子树的结点个数
        n = nodeCountPre1(t.rchild);        //遍历求右子树的结点个数
        return k + m + n;
    }

    public static int nodeCountIn(MyBTree bt) //基于中序遍历求结点个数
    {
        return nodeCountIn1(bt.b);
    }

    private static int nodeCountIn1(BTNode<Character> t) {
        int m, n, k;
        if (t == null)            //空树结点个数为0
            return 0;
        m = nodeCountIn1(t.lchild);        //遍历求左子树的结点个数
        k = 1;                    //根结点计数1，相当于访问根结点
        n = nodeCountIn1(t.rchild);        //遍历求右子树的结点个数
        return k + m + n;
    }

    public static int nodeCountPost(MyBTree bt) //基于后序遍历求结点个数
    {
        return nodeCountPost1(bt.b);
    }

    private static int nodeCountPost1(BTNode<Character> t) {
        int m, n, k;
        if (t == null)            //空树结点个数为0
            return 0;
        m = nodeCountPost1(t.lchild);        //遍历求左子树的结点个数
        n = nodeCountPost1(t.rchild);        //遍历求右子树的结点个数
        k = 1;                    //根结点计数1，相当于访问根结点
        return k + m + n;
    }

    public static int nodeCount4(MyBTree bt)    //递归求解
    {
        return nodeCount41(bt.b);
    }

    private static int nodeCount41(BTNode<Character> t) {
        if (t == null) return 0;                //空树结点个数为0
        else return (nodeCount41(t.lchild) + nodeCount41(t.rchild) + 1);
    }

    public static MyBTree copyBTree1(MyBTree bt1) //基于先序遍历复制二叉树
    {
        MyBTree bt2 = new MyBTree();
        bt2.b = copyBTree11(bt1.b);
        return bt2;
    }

    private static BTNode<Character> copyBTree11(BTNode<Character> t1)//由t1复制产生t2
    {
        if (t1 != null) {
            BTNode<Character> t2 = new BTNode<Character>(t1.data); //复制根
            t2.lchild = copyBTree11(t1.lchild);    //递归复制左子树
            t2.rchild = copyBTree11(t1.rchild);    //递归复制右子树
            return t2;
        }
        return null;                //t1为空时返回null
    }

    public static int level1(MyBTree bt, char x) {
        return level11(bt.b, x, 1);
    }

    private static int level11(BTNode<Character> t, char x, int h) {
        if (t == null) return 0;        //空树不能找到该结点
        else if (t.data == x) return h;    //根结点即为所找,返回其层次
        else {
            int l = level11(t.lchild, x, h + 1);    //在左子树中查找
            if (l != 0) return l;            //左子树中找到了,返回其层次
            else return level11(t.rchild, x, h + 1);
            //左子树中未找到,再在右子树中查找
        }
    }

    public static int level2(MyBTree bt, char x) {
        return level21(bt.b, x);
    }

    private static int level21(BTNode<Character> t, char x) {
        if (t == null)            //空树不能找到该结点
            return 0;
        if (t.data == x)            //根结点值为x
            return 1;
        int leftl = (t.lchild == null ? 0 : level21(t.lchild, x));
        int rightl = (t.rchild == null ? 0 : level21(t.rchild, x));
        if (leftl < 1 && rightl < 1)        //左右子树都没有找到，返回0
            return 0;
        return Math.max(leftl, rightl) + 1;    //返回左右子树中最大层次+1
    }

    public void preOrder2(MyBTree bt)        //先序遍历的非递归算法1
    {
        preOrder21(bt.b);
    }

    private void preOrder21(BTNode<Character> t) //被PreOrder2调用
    {
        Stack<BTNode> st = new Stack<BTNode>();     //定义一个栈
        BTNode<Character> p;
        st.push(t);                    //根结点t进栈
        while (!st.empty())            //栈不为空时循环
        {
            p = st.pop();                //出栈结点p
            System.out.print(p.data + " ");        //访问p结点
            if (p.rchild != null)            //p结点有右孩子时进栈
                st.push(p.rchild);
            if (p.lchild != null)            //p结点有左孩子时进栈
                st.push(p.lchild);
        }
    }

    public void preOrder3(MyBTree bt)        //先序遍历的非递归算法2
    {
        preOrder31(bt.b);
    }

    private void preOrder31(BTNode<Character> t)  //被PreOder3调用
    {
        Stack<BTNode> st = new Stack<BTNode>();      //定义一个栈
        BTNode<Character> p = t;
        while (!st.empty() || p != null)    //栈不空或者p不空时循环
        {
            while (p != null)            //访问根结点及所有左下结点并进栈
            {
                System.out.print(p.data + " ");     //访问p结点
                st.push(p);
                p = p.lchild;
            }
            if (!st.empty())             //若栈不空
            {
                p = st.pop();                 //出栈p结点
                p = p.rchild;                 //转向处理其右子树
            }
        }
    }

    public void inOrder2(MyBTree bt) { //中序遍历的非递归算法
        inOrder21(bt.b);
    }

    private void inOrder21(BTNode<Character> t) { //被InOrder2调用
        Stack<BTNode> st = new Stack<BTNode>();     //定义一个栈
        BTNode<Character> p = t;
        while (!st.empty() || p != null)    //栈不空或者p不空时循环
        {
            while (p != null)        //p及其所有左下结点并进栈
            {
                st.push(p);
                p = p.lchild;
            }
            if (!st.empty())            //若栈不空
            {
                p = st.pop();                //出栈p结点
                System.out.print(p.data + " ");    //访问p结点
                p = p.rchild;                //转向处理右子树
            }
        }
    }

    public void postOrder2(MyBTree bt) {  //后序遍历的非递归算法
        postOrder21(bt.b);
    }

    private void postOrder21(BTNode<Character> t) {
        Stack<BTNode> st = new Stack<BTNode>();    //定义一个栈
        BTNode<Character> p = t, q;
        boolean flag;
        do {
            while (p != null)            //p及其所有左下结点并进栈
            {
                st.push(p);
                p = p.lchild;
            }
            q = null;            //q指向前一个刚刚访问的结点或为空
            flag = true;            //表示在处理栈顶结点
            while (!st.empty() && flag) {
                p = st.peek();            //取当前栈顶结点
                if (p.rchild == q)        //若p结点右子树已访问或为空
                {
                    System.out.print(p.data + " ");    //访问p结点
                    st.pop();            //结点访问后退栈
                    q = p;            //让q指向则被访问的结点
                } else                //若p结点右子树没有遍历
                {
                    p = p.rchild;        //转向处理其右子树
                    flag = false;        //退栈，转向p结点的右子树
                }
            }
        } while (!st.empty());        //栈空结束
    }

    public void levelOrder(MyBTree bt)    //层次遍历的算法
    {
        BTNode<Character> p;
        Queue<BTNode> qu = new LinkedList<BTNode>(); //定义一个队列qu
        qu.offer(bt.b);            //根结点进队
        while (!qu.isEmpty())        //队不空循环
        {
            p = qu.poll();            //出队一个结点
            System.out.print(p.data + " ");    //访问p结点
            if (p.lchild != null)        //有左孩子时将其进队
                qu.offer(p.lchild);
            if (p.rchild != null)        //有右孩子时将其进队
                qu.offer(p.rchild);
        }
    }

    public static int kCount2(MyBTree bt, int k) //解法1
    {
        int cnt = 0;                //累计第k层结点个数
        class QNode                //队列元素类（内部类）
        {
            int lno;                //结点的层次
            BTNode<Character> node;    //结点引用

            public QNode(int l, BTNode<Character> no) {
                lno = l;
                node = no;
            }
        }
        Queue<QNode> qu = new LinkedList<QNode>();  //定义一个队列qu
        QNode p;
        qu.offer(new QNode(1, bt.b));    //根结点(层次为1)进队
        while (!qu.isEmpty())        //队不空循环
        {
            p = qu.poll();            //出队一个结点
            if (p.lno > k)            //当前结点的层次大于k，返回
                return cnt;
            if (p.lno == k) cnt++;        //当前结点是第k层的结点,cnt增1
            else                //当前结点的层次小于k
            {
                if (p.node.lchild != null)    //有左孩子时将其进队
                    qu.offer(new QNode(p.lno + 1, p.node.lchild));
                if (p.node.rchild != null)    //有右孩子时将其进队
                    qu.offer(new QNode(p.lno + 1, p.node.rchild));
            }
        }
        return cnt;
    }

    public static int kCount3(MyBTree bt, int k)    //解法2
    {
        int cnt = 0;                //累计第k层结点个数
        Queue<BTNode> qu = new LinkedList<BTNode>();    //定义队列qu
        BTNode<Character> p, q = null;
        int curl = 1;                //当前层次,从1开始
        BTNode<Character> last;        //当前层中最右结点
        last = bt.b;                //第1层最右结点
        qu.offer(bt.b);            //根结点进队
        while (!qu.isEmpty())            //队不空循环
        {
            if (curl > k) return cnt;        //当层号大于k时返回cnt
            p = qu.poll();            //出队一个结点
            if (curl == k) cnt++;        //是第k层的结点,cnt增1
            if (p.lchild != null)        //有左孩子时将其进队
            {
                q = p.lchild;
                qu.offer(q);
            }
            if (p.rchild != null)        //有右孩子时将其进队
            {
                q = p.rchild;
                qu.offer(q);
            }
            if (p == last)            //当前层的所有结点处理完毕
            {
                last = q;            //让last指向下一层的最右结点
                curl++;
            }
        }
        return cnt;
    }

    public static int kCount4(MyBTree bt, int k)    //解法3
    {
        if (k < 1) return 0;                    //k<1返回0
        Queue<BTNode> qu = new LinkedList<BTNode>();    //定义队列qu
        BTNode<Character> p, q = null;
        int curl = 1;            //当前层次,从1开始
        qu.offer(bt.b);        //根结点进队
        while (!qu.isEmpty())    //队不空循环
        {
            if (curl == k)        //当前层为第k层，返回队中元素个数
                return qu.size();
            int n = qu.size();    //求出当前层结点个数
            for (int i = 1; i <= n; i++)    //出队当前层的n个结点
            {
                p = qu.poll();        //出队一个结点
                if (p.lchild != null)    //有左孩子时将其进队
                    qu.offer(p.lchild);
                if (p.rchild != null)    //有右孩子时将其进队
                    qu.offer(p.rchild);
            }
            curl++;            //转向下一层
        }
        return 0;
    }


}
